/**
 * Definition for undirected graph.
 * struct UndirectedGraphNode {
 *     int label;
 *     vector<UndirectedGraphNode *> neighbors;
 *     UndirectedGraphNode(int x) : label(x) {};
 * };
 */
#include <map>
using namespace std;
class Solution {
    map<int, UndirectedGraphNode*> m;
    void run(UndirectedGraphNode *root){
        if (root==NULL) return;
        UndirectedGraphNode *copy=new UndirectedGraphNode(root->label);
        copy->neighbors.clear();
        m.insert(make_pair(root->label, copy));
        for (int i=0;i<root->neighbors.size();i++) {
            UndirectedGraphNode *child=root->neighbors[i];
            if (m.find(child->label)==m.end()) run(child);
            copy->neighbors.push_back(m.find(child->label)->second);
        }
    }
public:
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        if (node==NULL) return NULL;
        m.clear();
        run(node);
        UndirectedGraphNode *ret=m.find(node->label)->second;
        m.clear();
        return ret;
    }
};
